TIP

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并 (opens new window)。归并排序是一种稳定的排序方法。

最重要的可能需要处理的是将两个有序数组合并为一个有序数组

代码实现

public void mergeSort(int[] arr, int n) {
    subMergeSort(arr, 0, n - 1);
}

// 递归使用归并排序，对 arr[l...r] 的范围进行排序
private void subMergeSort(int[] arr, int l, int r) {
    if(l >= r)
        return;

    int mid = l + (r - l) / 2;
    subMergeSort(arr, l, mid);
    subMergeSort(arr, mid + 1, r);

    // 对已经有序的两部分进行归并
    merge(arr, l, mid, r);
}


// 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
private void merge(int[] arr, int l, int mid, int r) {
    // 辅助排序的数组
    int[] aux = new int[r - l + 1];
    for (int i = l; i <= r; i++)
        aux[i - l] = arr[i];

    int i = l, j = mid + 1;
    for (int k = l; k <= r; k ++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j ++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i ++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i ++;
        } else {
            arr[k] = aux[j - l];
            j ++;
        }
    }
}

归并排序的两个优化

• 在元素比较小的时候，其实这个时候更多的时候元素可能大部分都是有序的，所以这个时候可以引入【插入排序】这时可能整体的效率会更高

• 归并的前提 更多的是两个子数组是无序的，如有第二个数组的第一个元素，已经大于第一个数组的最后一个元素，就没有必要再进行归并过程了

  // 对已经有序的两部分进行归并, 只有当满足上面所说的条件再排序
  if (arr[mid + 1] < arr[mid])
  	merge(arr, l, mid, r);